package site.wanjiahao.map;

import site.wanjiahao.printer.BinaryTreeInfo;
import site.wanjiahao.printer.BinaryTrees;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Objects;
import java.util.concurrent.atomic.AtomicBoolean;

public class HashMap<K, V> implements Map<K, V> {

    // 红黑树容量
    private int size;

    // 存储红黑树根节点
    private Node[] tables;

    private static final int DEFAULT_INIT_CAPACITY = 1 << 4;

    // 默认装填因子
    private static final float DEFAULT_LOAD_FACTORY = 0.75f;

    public HashMap() {
        // 除去泛性数组创建规则
        tables = (Node[]) Array.newInstance(Node.class, DEFAULT_INIT_CAPACITY);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        if (size == 0) return;
        // 销毁内存
        size = 0;
        Arrays.fill(tables, null);
    }

    @Override
    public V put(K key, V value) {
        // 扩容
        resize();
        // 计算当前key，对应hash表的索引位置
        int index = index(key);
        Node node = tables[index];
        if (node == null) {
            // 第一次添加，创建红黑树根节点
            tables[index] = createNode(key, value, null);
            size++;
            fixAfterPut(tables[index]);
            return null;
        }

        Node parent;
        int hash = hash(key);
        Node result;
        boolean searched = false;
        int compareRes;
        do {
            if (node.hash > hash) {
                compareRes = 1;
            } else if (node.hash < hash) {
                compareRes = -1;
            } else if (Objects.equals(node.key, key)) {
                compareRes = 0;
            } else if (key != null &&
                    node.key instanceof Comparable &&
                    node.key.getClass() == key.getClass() &&
                    (compareRes = ((Comparable) node.key).compareTo(key)) != 0) {
            } else if (searched) {
                // 不存在当前元素
                compareRes = System.identityHashCode(node.key) - System.identityHashCode(key);
            } else if ((result = node(node.right, key)) != null || (result = node(node.left, key)) != null) {
                // 找到当前元素，覆盖
                compareRes = 0;
                node = result;
            } else {
                searched = true;
                // 不存在当前元素
                compareRes = System.identityHashCode(node.key) - System.identityHashCode(key);
            }

            if (compareRes > 0) {
                parent = node;
                node = node.left;
            } else if (compareRes < 0) {
                parent = node;
                node = node.right;
            } else {
                V oldValue = node.value;
                node.key = key;
                node.value = value;
                return oldValue;
            }
        } while (node != null);


        Node setNode = createNode(key, value, parent);
        if (compareRes > 0) {
            parent.left = setNode;
        } else {
            parent.right = setNode;
        }
        size++;
        fixAfterPut(setNode);
        return null;
    }

    @Override
    public V get(K key) {
        int index = index(key);
        Node node = node(tables[index], key);
        return node == null? null: node.value;
    }

    @Override
    public V remove(K key) {
        int index = index(key);
        // 判断当前节点的度
        Node node = node(tables[index], key);
        if (node == null) return null;

        Node willNode = node;
        V oldValue = null;

        if (hasTwoChildren(node)) {
            // 度为2：先找到对应的前驱（后继）节点，覆盖删除的节点，然后在删除对应的前驱（后继）节点（只存在度为1或者度为2）
            Node successor = successor(node);
            // predecessor不存在为空
            oldValue = node.value;
            node.key = successor.key;
            node.value = successor.value;
            node.hash = successor.hash;
            node = successor;
        }

        // 度为1：当前节点为父节点的什么节点，当前节点的子节点，作为这个节点存在
        Node replacement = node.left != null ? node.left : node.right;
        if (replacement != null) {
            replacement.parent = node.parent;
            // 度为1
        }
        if (node.isLeftNode()) {
            node.parent.left = replacement;
        } else if (node.isRightNode()) {
            node.parent.right = replacement;
        } else {
            tables[index] = replacement;
        }
        size--;

        fixAfterRemove(node, replacement);

        afterRemove(node, willNode);
        return oldValue != null? oldValue: node.value;
    }



    @Override
    public boolean containsKey(K key) {
        int index = index(key);
        return node(tables[index], key) != null;
    }

    @Override
    public boolean containsValue(V v) {
        AtomicBoolean atomicBoolean = new AtomicBoolean();
        traversal(new Consumer<K, V>() {
            @Override
            public boolean accept(K key, V value) {
                if (Objects.equals(value, v)) {
                    atomicBoolean.set(true);
                    return true;
                }
                return false;
            }
        });
        return atomicBoolean.get();
    }

    @Override
    public void traversal(Consumer<K, V> consumer) {
        if (consumer == null) return;
        LinkedList<Node> queue = new LinkedList<>();

        for (Node table : tables) {
            Node node = table;
            if (node != null) {
                queue.offer(node);

                while (!queue.isEmpty()) {
                    node = queue.poll();
                    if (consumer.accept(node.key, node.value)) return;

                    if (node.left != null) queue.offer(node.left);

                    if (node.right != null) queue.offer(node.right);
                }
            }
        }
    }

    protected void afterRemove(Node node, Node willNode) {

    }

    public void print() {
        for (Node table : tables) {
            if (table != null) {
                BinaryTrees.print(new BinaryTreeInfo() {
                    @Override
                    public Object root() {
                        return table;
                    }

                    @Override
                    public Object left(Object node) {
                        return ((Node) node).left;
                    }

                    @Override
                    public Object right(Object node) {
                        return ((Node) node).right;
                    }

                    @Override
                    public Object string(Object node) {
                        return node;
                    }
                });

                System.out.println();
                System.out.println("---------------------------------------");
            }
        }
    }

    private void resize() {
        // 判断是否需要扩容
        if (size / tables.length <= DEFAULT_LOAD_FACTORY) return;

        // 扩容为原来的两倍大小
        int newLength = tables.length << 1;
        Node[] oldTables = tables;
        tables = (Node[] )Array.newInstance(Node.class, newLength);
        // 遍历元素，挪动到原来的位置
        LinkedList<Node> queue = new LinkedList<>();
        for (Node table : oldTables) {
            if (table == null) continue;

            queue.add(table);
            while (!queue.isEmpty()) {
                Node node = queue.poll();

                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);

                // 移动节点，到新的hash表上
                removeNode(node);
            }
        }
    }

    protected Node createNode(K key, V value, Node parent) {
        return new Node(key, value, parent);
    }

    // 节点全盘移动
    private void removeNode(Node addNode) {
        // 至空数据
        addNode.left = addNode.right = addNode.parent = null;
        addNode.color = Node.RED;
        addNode.hash = hash(addNode.key);

        // 计算新的索引
        int index = index(addNode.key);
        Node node = tables[index];
        if (node == null) {
            // 第一次添加，创建红黑树根节点
            tables[index] = addNode;
            fixAfterPut(tables[index]);
            return;
        }

        Node parent;
        int compareRes;
        do {
            if (node.hash > addNode.hash) {
                compareRes = 1;
            } else if (node.hash < addNode.hash) {
                compareRes = -1;
            }  else if (addNode.key != null &&
                    node.key instanceof Comparable &&
                    node.key.getClass() == addNode.key.getClass()) {
                compareRes = ((Comparable) node.key).compareTo(addNode.key);
            } else  {
                // 不存在当前元素
                compareRes = System.identityHashCode(node.key) - System.identityHashCode(addNode.key);
            }

            if (compareRes > 0) {
                parent = node;
                node = node.left;
            } else {
                parent = node;
                node = node.right;
            }
        } while (node != null);

        addNode.parent = parent;
        if (compareRes > 0) {
            parent.left = addNode;
        } else {
            parent.right = addNode;
        }

        fixAfterPut(addNode);
    }

    private void fixAfterPut(Node node) {
        // 如果是根节点
        Node parent = node.parent;
        if (parent == null) {
            // 染色
            black(node);
            return;
        }

        // 如果父节点为黑色
        if (isBlack(parent)) {
            // 直接添加，不做处理
            return;
        }

        // 父节点是红色
        Node uncle = parent.sibling();
        // 祖父染红
        Node grand = red(parent.parent);
        if (isBlack(uncle)) {
            // uncle 不是红色 旋转处理
            if (parent.isLeftNode()) {
                if (node.isRightNode()) {
                    // LR
                    parent.rotateLeft();
                    parent = node;
                }
                // LL
                grand.rotateRight();
            } else {
                if (node.isLeftNode()) {
                    // RL
                    parent.rotateRight();
                    parent = node;
                }
                // RR
                grand.rotateLeft();
            }
            // 父亲染黑
            black(parent);
        } else {
            // uncle 是红色 上溢处理
            black(parent);
            black(uncle);
            fixAfterPut(grand);
        }
    }

    private void fixAfterRemove(Node node, Node replacement) {
        Node parent = node.parent;

        if (isRed(node)) {
            // 删除红色节点，不用做任何处理
            return;
        }

        if (replacement != null) {
            // 删除黑色节点，并且黑色节点存在替代节点
            // 替代节点染黑，其余不用做任何处理
            black(replacement);
            return;
        }

        // 删除的是根节点
        if (parent == null) return;

        // 删除单个黑色节点，做下移处理
        boolean left = parent.left == null || node.isLeftNode();
        Node sibling = left ? parent.right : parent.left;
        if (left) {
            // 当前节点在左边
            if (isRed(sibling)) {
                // 兄弟节点是红色
                black(sibling);
                red(parent);
                // 变成兄弟节点为黑节点情况
                parent.rotateLeft();
                sibling = parent.right;
            }
            if (sibling == null) return;
            // 兄弟节点是黑节点
            if (isRed(sibling.left) || isRed(sibling.right)) {
                if (isBlack(sibling.right)) {
                    // RL
                    sibling.rotateRight();
                    sibling = parent.right;
                }
                // RR
                parent.rotateLeft();
                // 染色
                color(sibling, colorOf(parent));
                color(sibling.left, Node.RED);
                color(sibling.right, Node.RED);
            } else {
                // 左右无节点，合并操作
                if (isBlack(parent)) {
                    red(sibling);
                    fixAfterRemove(parent, null);
                } else {
                    black(parent);
                    red(sibling);
                }
            }
        } else {
            // 当前节点在右边
            if (isRed(sibling)) {
                // 兄弟节点是红色
                black(sibling);
                red(parent);
                // 变成兄弟节点为黑节点情况
                parent.rotateRight();
                sibling = parent.left;
            }
            if (sibling == null) return;
            // 兄弟节点是黑节点
            if (isRed(sibling.left) || isRed(sibling.right)) {
                if (isBlack(sibling.left)) {
                    // LR
                    sibling.rotateLeft();
                    sibling = parent.left;
                }
                // LL
                parent.rotateRight();
                // 染色
                color(sibling, colorOf(parent));
                color(sibling.left, Node.RED);
                color(sibling.right, Node.RED);
            } else {
                // 左右无节点，合并操作
                if (isBlack(parent)) {
                    red(sibling);
                    fixAfterRemove(parent, null);
                } else {
                    black(parent);
                    red(sibling);
                }
            }
        }
    }

    private Node successor(Node node) {
        // 当前节点是否有左节点
        if (node.right != null) {
            node = node.right;
            while (node.left != null) {
                node = node.left;
            }
            // 循环终止，当前节点为前驱节点
            return node;
        } else if (node.parent != null) {
            // 父节点的右节点为当前节点，则为前驱节点
            while (node.parent != null && node.parent.left != node) {
                node = node.parent;
            }
            return node.parent;
        } else {
            // 左节点也为空，父节点为空，无前驱节点
            return null;
        }
    }

    private boolean hasTwoChildren(Node node) {
        return node.left != null && node.right != null;
    }

    // 根据当前k的hash值，找到下面的节点
    private Node node(Node node, K key) {
        if (node == null) return null;
        int hash = hash(key);
        int compareRes;
        Node result;
        while (node != null) {
            if (node.hash > hash) {
                node = node.left;
            } else if (node.hash < hash) {
                node = node.right;
            } else if (Objects.equals(node.key, key)) {
                // 找到当前节点
                return node;
            } else if (key != null &&
                    node.key instanceof Comparable &&
                    node.key.getClass() == key.getClass() &&
                    (compareRes = ((Comparable) node.key).compareTo(key)) != 0) {
                if (compareRes > 0) node = node.left;
                if (compareRes < 0) node = node.right;
                // 递归始终明确，该方法是干什么的，其他别管，想的头晕
            } else if (node.right != null && (result = node(node.right, key)) != null) {
                return result;
            } else {
                node = node.left;
            }
        }
        return null;
    }

    // 根据key，计算index索引位置
    private int index(K k) {
        if (k == null) return 0;
        int hashCode = k.hashCode();
        // 再次进行hash值的扰动计算
        return (hashCode ^ hashCode >>> 16) & (tables.length - 1);
    }

    // 根据key计算扰动值
    private int hash(K k) {
        if (k == null) return 0;
        return (k.hashCode() ^ k.hashCode() >>> 16);
    }

    // 自定义工具方法
    private int colorOf(Node node) {
        return node == null ? Node.BLACK : node.color;
    }

    private Node color(Node node, int color) {
        if (node != null) {
            node.color = color;
        }
        return node;
    }

    private boolean isBlack(Node node) {
        return colorOf(node) == Node.BLACK;
    }

    private boolean isRed(Node node) {
        return colorOf(node) == Node.RED;
    }

    private Node black(Node node) {
        return color(node, Node.BLACK);
    }

    private Node red(Node node) {
        return color(node, Node.RED);
    }

    protected class Node {

        private static final int BLACK = 1;

        private static final int RED = 0;

        K key;

        V value;

        int hash;

        Node left;

        Node right;

        Node parent;

        // 默认添加红色节点，比较符合红黑树性质
        int color = RED;

        public Node(K key, V value, Node parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
            this.hash = hash(key);
        }

        public boolean isLeftNode() {
            return this.parent != null && (this.parent.left == this);
        }

        public boolean isRightNode() {
            return this.parent != null && (this.parent.right == this);
        }

        public Node sibling() {
            if (this != null) {
                if (isLeftNode()) {
                    return parent.right;
                }
                if (isRightNode()) {
                    return parent.left;
                }
            }
            return null;
        }

        public void rotateLeft() {
            Node next = this.right;
            this.right = next.left;
            next.left = this;

            rotateAfter(this, next, this.right);
        }

        public void rotateRight() {
            Node next = this.left;
            this.left = next.right;
            next.right = this;

            rotateAfter(this, next, this.left);
        }


        public void rotateAfter(Node cur, Node next, Node node) {
            Node parent = cur.parent;
            next.parent = parent;
            if (parent == null) {
                tables[index(cur.key)] = next;
            } else if (cur.isLeftNode()) {
                cur.parent.left = next;
            } else if (cur.isRightNode()) {
                cur.parent.right = next;
            }
            cur.parent = next;
            if (node != null) {
                node.parent = cur;
            }
        }

        @Override
        public String toString() {
            return key + "__" + value;
        }
    }
}
